package cn.zhl.heap.binary;

import cn.zhl.heap.Heap;

import java.util.Comparator;


/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-05-26 15:44
 **/
public class BinaryHeap<T> implements Heap<T> {
	private int size;
	private static final int DEFAULT_CAPACITY = 10;
	private T[] table;

	private Comparator<T> comparator;

	public BinaryHeap(){
		this(null);
	}

	public BinaryHeap(Comparator comparator){
		this.comparator = comparator;
		table = (T[]) (new Object[DEFAULT_CAPACITY]);
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void add(T t) {
		ensureCapacity();
		table[size++] = t;
		up(size);
	}

	private void up(int size){
		
	}
	private void ensureCapacity(){
		int capacity = table.length;
		if(size+1>=capacity){
			capacity = capacity + (capacity >> 1);
			changeTable(capacity);
		}else if(size >= DEFAULT_CAPACITY && size < (capacity>>1)){
			changeTable(capacity);
		}
	}
	private void changeTable(int capacity){
		T[] newTable = (T[]) (new Object[capacity]);
		for(int i = 0;i<size;i++){
			newTable[i] = table[i];
		}
		table = newTable;
	}


	@Override
	public T remove(T t) {
		return null;
	}

	@Override
	public T get() {
		return null;
	}

	private int compareTo(T t1,T t2){
		return comparator==null?((Comparable)t1).compareTo(t2):comparator.compare(t1,t2);
	}
}
